// 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
// 请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
// 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
// 输出：4
// 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

// 思路，动态规划
// 五部曲
// 1. `dp[i][j]`表示最多有i个0和j个1的最大子集大小
// 2. 递推公式，`dp[i][j]`可以由上个strs的字符串推导而来，字符串有zeroNum个0，oneNum个1，`dp[i][j] = Math.max(dp[i][j], dp[i-zeroNum][j-onenNum] + 1)`
// 3. dp初始化为0
// 4. 遍历顺序，外层遍历为物品，内层为m和n的背包倒序遍历
// 5. 举例推导

function findMaxForm(strs, m, n) {
    let dp = new Array(m + 1).fill(0).map(_ => new Array(n + 1).fill(0))
    for (const str of strs) {
        let zeroCount = 0
        let oneCount = 0
        for (let i = 0; i < str.length; i++) {
            if (str[i] === '0') {
                zeroCount++
            }            
            if (str[i] === '1') {
                oneCount++
            }
        }
        // 倒序遍历，保证i，j的dp只会被统计一次
        for (let i = m; i >= zeroCount; i--) {
            for (let j = n; j >= oneCount; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeroCount][j - oneCount] + 1)                
            }            
        }
    }
    return dp[m][n]
}

let strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
console.log(findMaxForm(strs, m, n))